package search

/**
二叉排序树
*/

type BSTreeNode struct {
	value  int
	rchild *BSTreeNode
	lchild *BSTreeNode
}

func NewBSTreeNode(value int) *BSTreeNode {
	return &BSTreeNode{
		value: value,
	}
}

type BSTree struct {
	pRoot *BSTreeNode
}

func NewBSTree() *BSTree {
	return &BSTree{

	}
}

/**
非递归算法，插入节点
*/
func (bsTree *BSTree) InsertNode(value int) {
	node := NewBSTreeNode(value)

	if bsTree.pRoot == nil {
		bsTree.pRoot = node
		return
	}

	pNode, pNodeNext := bsTree.pRoot, bsTree.pRoot //插入节点,遍历节点
	for ; pNodeNext != nil; {
		pNode = pNodeNext
		if value >= pNodeNext.value {
			pNodeNext = pNodeNext.rchild
			if pNodeNext == nil {
				pNode.rchild = node
			}
		} else {
			pNodeNext = pNodeNext.lchild
			if pNodeNext == nil {
				pNode.lchild = node
			}
		}
	}
}

/**
查找
比较经过, 是否查找到
*/
func (bsTree *BSTree) Search(value int) ([]int, bool) {
	pNode := bsTree.pRoot //遍历节点
	reverse := make([]int, 0)
	for ; pNode != nil; {
		reverse = append(reverse, pNode.value)
		if pNode.value == value {
			return reverse, true
		} else if pNode.value > value {
			pNode = pNode.lchild
		} else {
			pNode = pNode.rchild
		}
	}

	return reverse, false
}
